package com.shangguigu.binarytree;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author: ZhouBert
 * @date: 2019/10/26
 * @description: 堆排序
 * todo:大顶堆-arr[i]>=arr[i<<1+1]&&arr[i]>=arr[i<<1+2]
 * todo:小顶堆-arr[i]<=arr[i<<1+1]&&arr[i]<=arr[i<<1+2]
 * TODO:难点：将无序数组转为大顶堆/小顶堆
 */
public class HeapSort {

	/**
	 * 完成堆排序
	 */
	public void heapSort(int[] arr) {
		///1.判断临界
		if (arr==null||arr.length==0){
			return;
		}

		///2.完成首次大顶堆
		maxHeap(arr);
		int temp=arr[0];
		///3.移位完成整个排序
		for (int i = arr.length-1; i > 0; i--) {
			arr[0]=arr[i];
			arr[i]=temp;
			adjustHeap(arr, 0,i);
			temp=arr[0];
		}
	}

	/**
	 * 完成首次大顶堆
	 * @param arr
	 */
	public void maxHeap(int[] arr) {
		///复杂度n*log n
		///找到父节点公式 (n-1)/2
		for (int k = (arr.length - 2) / 2; k >= 0; k--) {
			adjustHeap(arr, k, arr.length);
		}
	}

	/**
	 * 将一个叶子节点调整成大顶堆(并且将堆顶元素调整到正确的位置！)
	 *
	 * @param arr    待调整数组
	 * @param index  非叶子节点在数组中的索引
	 * @param length 需要处理的数组的长度(由于排序后会将堆顶放在数组尾部)
	 */
	public void adjustHeap(int[] arr, int index, int length) {
		///临时变量记录当前元素
		int temp = arr[index];

		///遍历左节点
		for (int k = (index << 1) + 1; k < length; k = (k << 1) + 1) {
			///找到左右节点中更大的索引位置
			if (k + 1 < length && arr[k] < arr[k + 1]) {
				k++;
			}
			///如果比较小，进行替换
			if (temp < arr[k]) {
				arr[index] = arr[k];
				///指向现在堆顶元素的位置
				index = k;
			} else {
				break;
			}
		}
		///调整堆顶元素
		arr[index] = temp;
	}

	/**
	 * 将一部分调整为大顶堆
	 */
	@Test
	public void testAdjustHeap() {
		int[] arr = {4, 6, 8, 5, 9};
		adjustHeap(arr, 1, arr.length);
		System.out.println(Arrays.toString(arr));
	}

	/**
	 * 测试最大堆
	 */
	@Test
	public void testMaxHeap() {
		int[] arr = {4, 6, 8, 5, 9};
		maxHeap(arr);
		System.out.println(Arrays.toString(arr));
	}

	@Test
	public void testHeapSort(){
		int[] arr = {4, 6, 8, 5, 9};
		arr= new int[]{88, 7, 5, 66, -99, 100};
		heapSort(arr);
		System.out.println(Arrays.toString(arr));
	}
}
